|
Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory, and is named after Emanuel Sperner, who published it in 1928. This result is sometimes called Sperner's lemma, but the name "Sperner's lemma" also refers to an unrelated result on coloring triangulations. To differentiate the two results, the result on the size of a Sperner family is now more commonly known as Sperner's theorem. ==Statement== A family of sets that does not include two sets ''X'' and ''Y'' for which ''X'' ⊂ ''Y'' is called a Sperner family. For example, the family of ''k''-element subsets of an ''n''-element set is a Sperner family. No set in this family can contain any of the others, because a containing set has to be strictly bigger than the set it contains, and in this family all sets have equal size. The value of ''k'' that makes this example have as many sets as possible is ''n''/2 if ''n'' is even, or the nearest integer to ''n''/2 if ''n'' is odd. For this choice, the number of sets in the family is . Sperner's theorem states that these examples are the largest possible Sperner families over an ''n''-element set. Formally, the theorem states that, for every Sperner family ''S'' whose union has a total of ''n'' elements, : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sperner's theorem」の詳細全文を読む スポンサード リンク
|